1. Field of the Invention
The present invention relates to computer-aided design tools. More particularly, the present invention relates to the simulation of circuits using a hierarchical data structure and applying isomorphism matching to skip computations on duplicate subcircuit behavior.
2. Description of the Related Art
Device-level circuit simulation is an important step in microelectronic circuit design. Through such simulation, the functionality of a circuit may be validated and performance of the circuit may be predicted before the circuit is physically fabricated. The application of existing simulation tools such as SPICE, however, is limited to the simulation of small subcircuit blocks, typically less than 100,000 transistors, due to their memory capacity and performance limitations.
The capacity of existing simulators is primarily determined by the size of the circuit being simulated. Although circuits are hierarchically structured, the circuit hierarchy is typically flattened to the device level during simulation. As a result, the device connectivity and device parameters are stored during simulation for each device. This is particularly important since there is a fixed memory overhead measured in bytes per device. It follows that memory usage during circuit simulation is approximately proportional to the circuit size measured in number of devices in the circuit. In existing simulators, the memory usage per device is in the order of hundreds of bytes. This means that approximately 1 G bytes (one billion bytes) of memory are required in order to simulate a circuit containing 10 million devices, assuming 100 bytes of memory are required per device. The excessive memory usage therefore makes it impractical to use existing circuit simulators to perform full-chip circuit simulation on today""s VLSI circuits. For example, a 256 M DRAM chip contains more than 256 million transistors and no existing circuit simulator can perform the full-chip simulation on the 256 M DRAM circuit. This memory limitation therefore forces microelectronic circuit designers to partition the full-chip design into blocks of smaller subcircuits which can be simulated by existing circuit simulators. Thus, the circuit is partitioned into subcircuits and the separate simulation results for the partitioned subcircuits are relied upon to predict the full-chip circuit behavior. However, the circuit partitioning is a tedious and error-prone task and thus reduces the designer""s productivity. Moreover, the simulated subcircuit behavior obtained by local subcircuit simulation may be different from that obtained if the subcircuit is simulated together with all other subcircuits. Accordingly, it would be desirable if large microelectronic circuits could be simulated without such partitioning.
As described above, the size of the circuit that may be simulated using currently available circuit simulators is limited. However, even those circuits that can be simulated using currently available circuit simulators require a substantial amount of simulation time as well as memory. This becomes evident from the fact that the behavior of a circuit, as well as the behavior of each subcircuit, is formulated into a set of mathematical equations which are solved during simulation. Typically, the circuit hierarchy is flattened to the device level and numerical analysis is applied to the mathematical equations that are formulated from the flattened data. Since the mathematical equations are formulated at the device level, the computations required increase with the number of devices in the circuit. However, as described above, a large circuit may contain millions of devices and therefore the electrical behavior of the circuit may be expressed by millions of equations. As a result, the circuit can be time-consuming to simulate. Accordingly, the cost of testing such a circuit is non-trivial.
Although simulators having reduced simulation time have been developed, such improvements have generally been achieved through relaxing the accuracy of the simulation results. In addition, some simulators such as PowerMill available from Synopsys Inc., located in Mountain View, Calif. have achieved an increase in circuit simulation speed by taking advantage of circuit latency found in digital CMOS circuits. Thus, these simulators skip computations for idle subcircuits. However, the applicability of such simulators is limited to digital CMOS circuits. In addition, the assumption of circuit latency is getting invalidated by analog behavior arising in today""s deep submicron technology. For example, due to noise from crosstalk capacitances, each device could be physically active all the time even though it is functionally idle most of the time. Therefore, although SPICE and other faster circuit simulators continue to play a critical role in microelectronic circuit simulation, the demand for more efficient circuit simulation is increasing.
To meet the challenge of simulating very large circuits containing millions of transistors, a simulation technology known as macromodeling has been implemented. Through the use of macromodeling, the electrical behavior of a subcircuit is characterized and the subcircuit is replaced by its behavioral model. Since this approach skips the details of a subcircuit and replaces it with an abstract model, the macromodeling approach consumes a minimal amount of memory. In addition, the simulation speed is much faster since it operates on a simpler behavioral description instead of massive numerical data. Theoretically, this approach can therefore be used to simulate a circuit of unlimited size. However, such approximate characterization of subcircuit behavior cannot accurately simulate the behavior of the entire circuit. Moreover, this approach requires a nontrivial effort to build the model since the modeling process is circuit dependent. Model characterization is tedious and time-consuming since it needs to include different combinations of input patterns and output load conditions. In addition, the subcircuit must be recharacterized whenever the subcircuit topology and circuit parameters change. Due to the difficulty in building the behavioral model, this macro-modeling approach is limited to applications where the subcircuit size is small or the subcircuit behavior is less sensitive to the surrounding environment. It would therefore be desirable if circuit simulation could be performed without such characterization.
In view of the above, it would be desirable if the simulation time and memory consumed during circuit simulation could be reduced. Moreover, a new technology is needed to allow a circuit simulator to perform full-chip simulation on circuits containing hundreds of million transistors, whether such circuits exist today or will emerge in the next decade.
The present invention implements methods and apparatus for validating the functionality and performance of microelectronic circuits prior to fabrication. More particularly, the present invention may be advantageously used to accurately simulate the electrical behavior of very large microelectronic circuits. This is accomplished, in part, through exploiting the hierarchical architecture in microelectronic circuit design.
Currently available circuit simulators have not used the hierarchical architecture of microelectronic circuits to benefit the simulation process. Rather, even when a hierarchical data structure is produced from a netlist representing the circuit being simulated, the hierarchical data structure is typically flattened during the simulation process. In other words, the memory required during simulation is proportional to the number of devices in the circuit being simulated. Similarly, the number of computations performed during the simulation process increases with the number of devices in the circuit. In order to reduce the simulation time and memory required during simulation, the circuit is often partitioned. However, such partitioning can introduce errors into the simulation process and therefore reduces the accuracy of the resulting simulation.
In order to utilize the hierarchical architecture to simulate the electrical behavior of a circuit, the present invention uses a hierarchical data structure throughout the simulation process. More particularly, a netlist describing the circuit may be parsed to permit the information in the netlist to be stored in a hierarchical data structure. However, it is particularly important that the hierarchical data structure be constructed in a manner that facilitates the simulation process. As will be described below, through the use of such a hierarchical data structure, memory requirements as well as the number of computations performed during simulation may be dramatically reduced.
According to the present invention, the hierarchical data structure is designed to maximize the benefits that may be obtained from the hierarchical architecture of microelectronic circuits. In many circuits, identical subcircuits are often used multiple times within the same circuit. By way of example, an inverter may be used repeatedly within a circuit. As yet another example, in memory arrays, numerous memory cells may be used within a single memory circuit. As a result, these identical subcircuits may share a common circuit structure or subcircuit definition. By way of example, a subcircuit definition may describe the topology of the subcircuit as well as the device parameters of the subcircuit (e.g., resistance, capacitance, and transistor size). Alternatively, the device parameters may be specified in corresponding element definitions provided in leaf nodes that are linked to the subcircuit definition. According to one embodiment, the topology of the subcircuit is represented by a block matrix. Since multiple child subcircuits may be associated with a single subcircuit definition, it is desirable to combine such subcircuits or xe2x80x9cinstancesxe2x80x9d in memory. Thus, multiple subcircuits may share a single static circuit storage area in which the subcircuit definition is stored. In this manner, memory consumed during the simulation process may be minimized.
While multiple circuits may share such static circuit storage, the circuits may have different node voltages at a specified time and therefore different xe2x80x9cdynamic voltage statesxe2x80x9d. Thus, a set of voltage states may be associated with each subcircuit definition. However, where node voltages are determined to be identical for more than one subcircuit during simulation, the subcircuits may also share a common dynamic voltage state. As a result, the voltage state associated with multiple nodes (e.g., child subcircuits) in the hierarchical data structure may be linked to a single voltage state. In this manner, memory use during simulation may be further reduced. It is important to note that through the use of the above-described hierarchical data structure, the memory storage required by the present invention is proportional to the number of different subcircuit types rather than the number of devices. In typical microelectronic circuits, the number of different subcircuit types is much less than the number of devices. By way of example, a standard 256 M DRAM circuit may contain 284 million devices and only 500 subcircuit types. Accordingly, the capacity limit faced by existing simulators is eliminated and the size of the circuit that may be simulated is therefore dramatically increased.
Where two subcircuits share a dynamic voltage state as well as a subcircuit definition, isomorphism may be applied to skip computations for these duplicate circuit blocks throughout the simulation process. According to one embodiment, the voltage state is updated for each subcircuit identified in the hierarchical data structure. As described above, each subcircuit is linked to a corresponding subcircuit definition and associated set of voltage states. As a result, the voltage state associated with a subcircuit need not be updated if the state has previously been updated for another subcircuit linked to the same subcircuit definition and voltage state. In other words, at a specific point in time during the simulation process, each one of the voltage states associated with a particular subcircuit definition need be updated only once, regardless of the number of subcircuits linked to the subcircuit definition and set of voltage states.
Once the voltage states have been updated, the device model is calculated for primitive elements in the circuit using the updated voltage states. As described above, where subcircuits share the same subcircuit definition and voltage state, the device model may be calculated a single time for the multiple subcircuits. Thus, the time required to calculate device models as well as total simulation time is dramatically reduced. Moreover, since the number of device model calculations during the simulation process is reduced, the memory required to store the reduced number of device model calculation results is similarly minimized.
Upon completion of the device model calculations, the behavior of the subcircuit may be simulated using the device model values and information associated with the subcircuit definition. More particularly, as described above, the behavior of each subcircuit may be represented by a set of equations in the form of a matrix. The matrix may then be loaded and solved using the device model calculations and the subcircuit definitions that are linked to the hierarchical data structure. According to one embodiment, a hierarchical block matrix is used to identify child subcircuits associated with each node in the hierarchical data structure. Once loaded with the appropriate values, the block matrices may be hierarchically solved. More particularly, the present invention may recursively simulate the behavior of each child subcircuit instance. Since most subcircuit instances not only share the same subcircuit definition but also exhibit the same behavior either throughout the simulation period or in sub-intervals of the simulation period, duplicate computations may be eliminated. By way of example, most sense amplifiers and core memory cells in memory circuits are observed to exhibit the same behavior during simulation. Thus, as indicated above, through the use of a hierarchical data structure, a circuit may be hierarchically simulated to skip the duplicate processing typically performed while simulating subcircuits with identical behavior. In this manner, the hierarchical nature of microelectronic circuits may be advantageously used to simulate the electrical behavior of a circuit while minimizing the simulation time and memory required. Accordingly, the present invention is superior to simulation tools that flatten the circuit hierarchy, particularly for circuits with a regular array structure such as memory circuits.
According to another aspect of the invention, the hierarchical netlist may be restructured to facilitate the simulation process. Where coupling between nodes in the circuit being simulated is equal to zero, the simulation process may be greatly simplified. This may become evident from examining a standard matrix. Where entries in the matrix are zero, the number of computations required is reduced. Thus, where coupling between the nodes in the circuit is represented by one or more entries in the matrix, it becomes evident that the number of computations may be greatly reduced where the coupling is zero. Through the use of equivalent impedance partitioning, it may be determined whether the coupling between nodes in the circuit may be approximated to zero and therefore effectively ignored during the simulation process. Thus, through examination of circuit parameters such as the equivalent resistance and frequency of operation of the circuit, it may be determined whether the coupling parameters may be approximated to zero.
Once it is determined whether the coupling parameters can be approximated to zero through the use of a method such as equivalent impedance partitioning, the hierarchical data structure may be modified through the use of a process such as hierarchical injection. Moreover, such restructuring may be limited to circuits that are large in size since restructuring may be unnecessary where the circuit and corresponding matrices are relatively easy to solve. According to one embodiment, such restructuring may be accomplished through the application of an algorithm such as the Min-Cut algorithm where a minimum number of nodes are selected and moved outside a subcircuit in order to partition the subcircuit. In this manner, subcircuits having an identical topology are created. Thus, it is likely that these newly created subcircuits may share both a subcircuit definition and a voltage state. Accordingly, memory requirements and simulation time may be minimized through preprocessing performed prior to transient simulation.
According to yet another aspect of the invention, simulation of the circuit is achieved without flattening the hierarchical data structure. In existing simulation technology, the circuit hierarchy is flattened to the device level and numerical analysis is applied to the mathematical equations formulated from the flattened data. As a result, memory requirements and computations are proportional to the number of devices in the circuit. However, as described above, the hierarchical data structure may be processed hierarchically such as through a recursive process in order to eliminate such unnecessary calculations and memory requirements.
The present invention provides methods and apparatus for simulating the electrical behavior of a circuit without flattening the circuit hierarchy. More particularly, simulation is performed through the use of a hierarchical data structure to advantageously exploit the hierarchical nature of electronic circuits. In this manner, the memory consumed as well as the computations performed during the simulation process are minimized. Thus, the present invention enables microelectronic circuit designers to perform full-chip circuit simulation in a reduced simulation time. Accordingly, through the use of the present invention, circuits with more than 100 million transistors can be simulated, whereas existing circuit simulators can typically simulate a circuit having up to one million transistors.